package main.图;

/**
 * @author tmh
 * @date 2024/9/23 18:51
 * @description
 */
public class T208实现Trie前缀树 {
}

class Trie {
    private Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int num = word.charAt(i) - 'a';
            if (node.children[num] == null) {
                //关键是看的这个，如果children为null，那么就初始化这个
                node.children[num] = new Node();
            }
            node = node.children[num];
        }
        node.isEnd = true;

    }

    public boolean search(String word) {
        Node node = searchPrefix(word);
        return node != null && node.isEnd;

    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;

    }

    private Node searchPrefix(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            node = node.children[word.charAt(i) - 'a'];
            if (node == null) {
                return null;
            }
        }
        return node;
    }
}

class Node {
    Node[] children;
    boolean isEnd;

    public Node() {
        children = new Node[26];
        isEnd = false;
    }
}
